package com.leetcode.LeetCode精选TOP面试题;

import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * @author 覃国强
 * @date 2022-06-29 16:55
 */
public class 题库_0139_单词拆分 {

  static
  class Solution {

    public boolean wordBreak(String s, List<String> wordDict) {
      if (s == null || s.length() == 0) {
        return true;
      }
      if (wordDict == null || wordDict.isEmpty()) {
        return false;
      }
//      return backtrack(s, 0, wordDict);
      return dp(s, wordDict);
    }

    private boolean dp(String s, List<String> wordDict) {
      Set<String> set = new HashSet<>(wordDict);
      boolean[] dp = new boolean[s.length() + 1];
      dp[0] = true;
      for (int i = 1; i <= s.length(); ++i) {
        for (int j = 0; j < i; ++j) {
          if (dp[j] && set.contains(s.substring(j, i))) {
            dp[i] = true;
            break;
          }
        }
      }
      return dp[s.length()];
    }

    private boolean backtrack(String s, int toffset, List<String> wordDict) {
      for (String prefix : wordDict) {
        if (s.endsWith(prefix) && toffset == s.length() - prefix.length()) {
          return true;
        }
        if (s.startsWith(prefix, toffset) && backtrack(s, toffset + prefix.length(), wordDict)) {
          return true;
        }
      }
      return false;
    }
  }

}
